package leetcode;

public class MergeKSortedList23 {
    class ListNode {
        int val;
        ListNode next;

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    // 合并多个有序链表
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) { // 这里超容易忘记 要考虑边界情况 如果数组为空
            return null;
        }
        return f(lists, 0, lists.length - 1);

    }

    // 合并多个有序链表递归实现
    public ListNode f(ListNode[] lists, int low, int high) {
        if (low == high) {
            return lists[low];
        }
        int m = (high + low) >>> 1;
        ListNode left = f(lists, low, m);
        ListNode right = f(lists, m + 1, high);
        return merge2(left, right);
    }

    // 合并两个list 指针
    public ListNode merge2(ListNode p1, ListNode p2) {
        ListNode s = new ListNode(-1, null);
        ListNode p = s;
        while (p1 != null && p2 != null) {
            if (p1.val < p2.val) {
                p.next = p1;
                p1 = p1.next;
                p = p.next;
            } else {
                p.next = p2;
                p2 = p2.next;
                p = p.next;
            }
        }
        if (p1 == null) {
            p.next = p2;
        }
        if (p2 == null) {
            p.next = p1;
        }
        return s.next;
    }

    // 合并两个list 递归
    public ListNode merge(ListNode p1, ListNode p2) {
        if (p1 == null) {
            return p2;
        }
        if (p2 == null) {
            return p1;
        }
        if (p1.val < p2.val) {
            p1.next = merge(p1.next, p2);
            return p1;
        } else {
            p2.next = merge(p1, p2.next);
            return p2;
        }
    }

    public static void main(String[] args) {
        ListNode[] list = new ListNode[2];
        MergeKSortedList23 m = new MergeKSortedList23();
        m.mergeKLists(list);

    }
}

